Search results for "Distribution sequences"

showing 1 items of 1 documents

The pruning-grafting lattice of binary trees

2008

AbstractWe introduce a new lattice structure Bn on binary trees of size n. We exhibit efficient algorithms for computing meet and join of two binary trees and give several properties of this lattice. More precisely, we prove that the length of a longest (resp. shortest) path between 0 and 1 in Bn equals to the Eulerian numbers 2n−(n+1) (resp. (n−1)2) and that the number of coverings is (2nn−1). Finally, we exhibit a matching in a constructive way. Then we propose some open problems about this new structure.

General Computer ScienceMatching (graph theory)Distribution sequences0102 computer and information sciencesFeasible sequences01 natural sciencesTheoretical Computer ScienceCombinatoricsCatalan numbersymbols.namesakeLattice (order)[MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO]0101 mathematicsComputingMilieux_MISCELLANEOUSMathematicsBinary tree010102 general mathematicsEulerian pathLatticesJoin (topology)Binary trees010201 computation theory & mathematicsShortest path problemPath (graph theory)symbolsCatalan numbersComputer Science(all)
researchProduct